package com.code.test.dance;

/**
 * https://www.nowcoder.com/questionTerminal/3a188e9c06ce4844b031713b82784a2a
 * <p>
 * <p>
 * 排序奇升偶降链表
 * <p>
 * 给定一个奇数位升序，偶数位降序的链表，返回对其排序后的链表。
 * <p>
 * 题面解释：例如链表 1->3->2->2->3->1 是奇数位升序偶数位降序的链表，而 1->3->2->2->3->2 则不符合题目要求。
 * <p>
 * 数据范围：链表中元素个数满足
 */
public class OddEvenSortLink {

    /**
     * 解题思路：
     * 1、先将链表拆成奇数位、偶数位 2条链表， O(n)
     * 2、偶数位原先是降序，反转成升序
     * 3、合并2个升序链表
     */
    public static void main(String[] args) {

    }

    public static LinkNode sortLinkedList(LinkNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        LinkNode oddCur = head;
        LinkNode evenCur = head.next;

        //
        LinkNode oddHead = oddCur;
        LinkNode evenHead = evenCur;

        while (evenCur != null) {
            //奇数节点挂到偶数的下一个
            oddCur.next = evenCur.next;
            if (oddCur.next != null) {
                /**
                 * 1→ 8→ 2→ 6→ 3→ 4→ 5→ 2
                 * 如果上面调整完，此时奇数的下一个不为空，
                 * 1→2→6
                 * oddCur 是1 1.next.next = 6
                 * 8→6
                 */
                evenCur.next = oddCur.next.next;
            }
            oddCur = oddCur.next;
            evenCur = evenCur.next;
        }
        evenHead = reverseList(evenHead);
        return mergeList(oddHead, evenHead);

    }

    // 反转链表
    private static LinkNode reverseList(LinkNode head) {
        if (head == null) return head;
        LinkNode prev = null;
        LinkNode cur = head;
        while (cur != null) {
            LinkNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    // 合并两个有序链表
    private static LinkNode mergeList(LinkNode head1, LinkNode head2) {
        LinkNode dummy = new LinkNode(-1);
        LinkNode cur = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        while (head1 != null) {
            cur.next = head1;
            head1 = head1.next;
            cur = cur.next;
        }
        while (head2 != null) {
            cur.next = head2;
            head2 = head2.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}
